Iteration
Volume Number: 1
Issue Number: 10
Column Tag: Lisp Listener
"Iteration Techniques in Lisp" 
By Andy Cohen, Human Factors Engineer, Hughes Aircraft, MacTutor
Contributing Editor
Last month I showed how ExperLisp uses some of the simpler Quickdraw routines.
For the curious, the following table contains all the Quickdraw routines discussed in
the ExperLisp Reference Guide.
Quickdraw Routines
CLOSEPOLY CLOSERGN COPYRGN
DIFFRGN DISPOSERGN DRAWCHAR
DRAWSTRING EMPTYRGN EQUALRGN
ERASEARC ERASEOVAL ERASEPOLY
ERASERECT ERASERGN
ERASEROUNDRECT FILLARC FILLOVAL
FILLRECT FILLRGN
FILLROUNDRECT FRAMEARC
FRAMEOVAL FRAMEPOLY FRAMERECT
FRAMERGN FRAMEROUNDRECT
GETFONTINFO HIDECURSOR HIDEPEN
INSETRGN INVERTARC INVERTOVAL
INVERTPOLY INVERTRECT INVERTRGN
INVERTROUNDRECT KILLPOLY LINE LINETO
MOVE MOVETO NEWRGN
OBSCURECURSOR OFFSETPOLY OFFSETRGN
PAINTARC PAINTOVAL PAINTPOLY
PAINTRECT PAINTRGN
PAINTROUNDRECT PENMODE PENNORMAL
PENPAT PENPOS PENSIZE
SECTRGN SETEMPTYRGN SETRECTRGN
SHOWCURSOR SHOWPEN SPACEEXTRA
TEXTFACE T EXTFONT
TEXTMODE TEXTSIZE
UNIONRGN XORRGN
Quickdraw commands will be discussed in more detail as each command is used
within the ExperLisp examples.
Iteration is a process which provides a method of performing repetitive actions.
In BASIC, iteration is accomplished with the FOR...NEXT or GOTO statements. Fortran
uses the DO loop and Pascal REPEAT.....UNTIL. Experlisp has a number of different
kinds of iteration, some of which look and act like those of the above.
The first kind of iteration requires use of the PROG special form. PROG stands for
program and has a list of variables associated with it that are equal to nil when the
PROG is evaluated. These variables are local and are bound to the PROG. The body of the
PROG follows the variable list. The body contains forms or lists which are evaluated
and consist of symbols, values or procedures. PROG by itself returns nil and it does not
provide iteration. The special form GO within PROG is used with an arbitrary tag for
iteration. The tag is placed where the loop begins within the PROG. GO tagname, placed
further along within the PROG, puts the next evaluation to where the tag is. For
example;
(defun iter () ;1
(prog ((y 1)) ;2
loop ;3
(setq y (add1 y)) ;4
(print y) ;5
(if (not(= 6 y)) (go loop)))) ;6
(iter)
When the above is compiled...
;iter
;2
;3
;4
;5
;6
;nil
The semicolon on each line of the sample is the method one uses for placing
remarks within ExperLisp source code. Everything after the semicolon is ignored. The
above PROG is within a defined procedure (iter). This makes it possible for the code to
be compiled and then called as a procedure. Multiple PROGs are allowed within a
DEFUN. However, the variables are local to each of the PROGs. It is wise to keep the
number of PROGS within a defined procedure down to a minimum. The smaller the
procedures, the easier to debug. Line 2 starts the PROG, declares the variable "y" and
gives "y" the value of 1. ExperLisp syntax requires the variable or variables and their
associated values be contained within an overall variable list. That is why the list "(y
1)" is contained within parentheses. Line 3 is the GO tag. Note, that it is not within it's
own list. However, it is within the overall PROG list. In line 4 the value of y has the
number 1 added to it. The value of this sum is then assigned to the symbol "y" using
SETQ. Line 5 prints the value of "y" for each loop. Line 6 tests to see if the value of "y
equals ten. If it doesnt then the evaluation is sent to the GO tag, "loop". The entire
process is then repeated until "(not(= 10 y))" returns "nil". If it does then the next
evaluation takes place after line 6. Since Line 6 is actually the end of the PROG, nil is
returned and the iteration is stopped. In order to get a value returned from a PROG one
must use RETURN. RETURN not only returns a value, it also terminates the iteration.
For example;
(defun iter (x)
(prog ((y 1))
loop
(setq y (add1 y))
(if(= x y) (RETURN "Y IS EQUAL TO X")
(print y))
(go loop)))
(iter 5)
In the above "x" is compared to "y". When found to be equal ExperLisp stops the
iteration and returns the string as follows;
;Iter
;2
;3
;4
;Y IS EQUAL TO X
Early versions of Lisp use PROG and GO for iteration. Later versions, which
strive to conform to the Common Lisp standard, are using a more efficient form of
iteration form called DO. DO not only specifies the variable label, it can indicate an
initial value, increment the value and contain a conditional for halting the iteration.
The syntax for the DO special form is as follows:
(DO ((Variable initial value
increment ) (Conditional))
(form)
(form)
....)
(Defun Iter2 (x)
(DO ((y 1 (add1 y)))
((= y x) "Y IS EQUAL TO X")
(Print y)))
The above is a DO version of the PROG sample, "Iter". It performs the same task
however, it's output is slightly different.
; (iter2 5)
;1
;2
;3
;4
;"Y IS EQUAL TO X
In the PROG version the addition of the number one to "y" is performed prior to
the print command. Hence, the first number printed is two. In the DO version the ADD1
procedure is not performed until the second loop. The print "y" statement is performed
in the first loop so that the number one is printed first. Note that when the conditional
"(= y x)" is true the iteration is halted and what follows the conditional is returned.
For another example, check out following:
(defun iterfun (x) ;1
(do ((a 0 (add1 a))) ;2
((= a 5) 'done) ;3
(print (* a x)))) ;4
(iterfun 3)
;iterfun
;0
;3
;6
;9
;12
;done
Line one of the above specifies the defined procedure and creates the symbol "x".
In line two the variable "a" is initialized and assigned the value zero. On that same line
the method of incrementation of the variable is also specified. Line three is the
conditional and tests the variable "a" for equivalence with the number five. Line four
prints the product of the value of "a" for each iteration and the value assigned to the
symbol, "x". One of the features of DO is that one may use GOs and RETURNs just as in
the PROG.
There is another form of DO for faster and simpler iteration. DOLIST assigns the
elements of a list to a symbol. It then performs the functions within it's body upon each
element of the list one at a time. It's syntax is as follows:
DOLIST (Symbol '(list)) (functions......)
(DOLIST (FUN '(Buy Mactutor Mag))
(print fun)
;Buy
;Mactutor
;Mag
;nil
The print command is performed upon each member of the list assigned to "FUN".
Note that it always returns nil when the iteration is complete. This is because the list
assigned to "FUN" is exhausted. The list then contains nil.
One of the easiest to use forms of iteration (e specially to someone who knows
BASIC) is DOTIMES. Using DOTIMES one specifies only a variable which represents
each loop and the maximum number of loops one wants performed. For example:
(Dotimes (turn 150)
(forward (/ turn 2))
(back (/ turn 2))
(right turn))
When compiled or typed into the Listener Window the above list produces the
following:
The symbol "turn" is initially zero. The body of DOTIMES is iterated 150 times. I
used 150 so that enough lines would be drawn to make it interesting. Remember
FORWARD? Well, BACK moves the pen backward. I divided "TURN" in half when the pen
is moved so that the lines don't go off the column's margins. I'll continue with another
form of iteration after the next couple of paragraphs.
Using the Mouse
Using the mouse as an input or interactive device with ExperLisp is quite simple.
GETMOUSE reports the X-Y coordinates of the mouse's's pointer on the active window.
Type the following in the Listener Window:
(GETMOUSE)
;(146 107 )
BUTTON is a predicate which returns "t" when it is evaluated and the mouse's
button is held down. It returns nil when the button is not held down. The following is an
example of GETMOUSE and BUTTON in iterative functions.
(defun Watch ()
(prog ()
look
(if ( button) (Mousey)
(go look))))
(defun Mousey ()
(prog ()
another
(print (getmouse))
(if (not( button))
(halt) (go another))))
(defun halt ()
(print"that's all folks!"))
(Watch)
The first of the three above procedures, Watch, waits for the mouse's button to be
pressed. If it is not then the loop continues. When the button is pressed then Watch
calls Mousey. Mousey will print the X-Y position of the mouse as long as the button is
held down (remember, "(IF (then) (else))" ?). When the button is released Mousey
calls Halt. Halt simply prints a message with no iteration.
One more form of iteration is the function, WHILE. WHILE includes a conditional.
If the conditional returns true then the body of the WHILE is performed. What makes
WHILE an iterative function and one that is different from those above, is that the
conditional repeats the test as long as it returns true or nonnil.For example:
(While (Not(Button)) (Print(Getmouse)))
The above performs alot like "Mousey" above. However it all takes place on one
line and operates from the mouse differently. Instead of showing the mouse's position
with the button down, the above shows until the button is pressed down.
One aspect of ExperLisp which might not be apparent to a novice is the fact that
once a procedure is defined via DEFUN, it is available until one quits ExperLisp.
ExperLisp is not just a language, it is an environment. If one was to compile all of the
samples in this month's issue, then each sample can be run by simply typing the
procedure's name within a list in the Listener Window. The value of this fact will be
more apparent after the discussion on menus in ExperLisp.
User Warning
In using ExperLisp one must be aware from the very beginning of a bug in
Experlisp's design of the user interface. When one tells the Mac to save from the menu
selection under "File", ExperLisp saves the active window into the active file. If one
has the Listener Window as the active window and tells ExperLisp to save, the entire
file will be replaced by the contents of the Listener Window. BE CAREFUL. Check which
window is active before you save. Eventually, later versions of ExperLisp will have a
"snapshot" feature. This feature will save the contents of the environment. One will be
able to get ExperLisp back to exactly where it was when the snapshot was taken without
recompiling files. This might be performed by saving with the Listener Window active.
If one has a couple of files compiled and is using them in conjunction, this feature will
save lots of time when saving and restarting ExperLisp.
Last month I described how one can measure a Lisp machine's capacity by seeing
how many cons cells it can handle. I also described the FREECONS procedure available
in the latest versions of ExperLisp (v1.02). I'd like to report that after upgrading my
512K Mac to 2 megabytes (from Levco in San Diego) I found that ExperLisp can have
as many as 30,440 cons cells. However, that many cons cells is far from necessary for
the simple examples contained in the Lisp Listener column. A 512K mac will do fine. In
writing this article though, I put Experlisp, Macwrite and Macpaint all into the
Switcher utility (v3.5). Most of which I load from a RAMdisk! No more waiting to boot
up the applications, verify code, or copy and paste. I have switcher allocate 500K to
ExperLisp and I can still access 5000 cons cells. When using the full two megabytes
one has as many cons cells as alot of the very expensive Lisp workstations. Note that
the upgrades of 1 or 2 megabytes available by most companies do not necessarily
access the extra memory in the same way. I can assure all those interested that the 2
megabyte (or Monster Mac) upgrade from Levco can access the extra RAM using
ExperLisp or most of the other applications which were designed in accordance with
the Macintosh guidelines.
Next month I will show how to use the Mouse in interacting with the Quickdraw
routines. I will also discuss recursion.